/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-bad-version
   @Language: C++
   @Datetime: 16-02-09 05:52
   */

/**
 * class SVNRepo {
 *     public:
 *     static bool isBadVersion(int k);
 * }
 * you can use SVNRepo::isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
 */
class Solution {
public:
	/**
	 * @param n: An integers.
	 * @return: An integer which is the first bad version.
	 */
	int findFirstBadVersion(int n) {
		// write your code here
		int begin=1, end=n, mid;
		while(begin<end){
			mid = (end-begin)/2+begin;
			if (SVNRepo::isBadVersion(mid)) end=mid;
			else begin=mid+1;
		}
		return begin;
	}
};
